A navigation system performs travel guidance for enabling a user to easily and quickly reach the selected destination. A typical example is a vehicle navigation system where a vehicle is equipped with a navigation function to guide a driver to a destination through a calculated route. Such a navigation system detects the position of the user's vehicle, and reads out map data pertaining to an area at the current vehicle position from a data storage medium, for example, a DVD (digital versatile disc), or a hard disc. Typically, the navigation system displays a map image on a screen while superimposing thereon a mark representing the current location of the user.
Namely, when a destination is set, a navigation system retrieves and processes the map data to produce a calculated route, which is an appropriate route to the destination determined by predefined methods. For example, the calculated route is determined based on the shortest way to reach the destination, the route preferring freeways to surface roads, the least expensive way to the destination, or the route without using toll road, and the like. Then, the navigation system performs the route guidance operation to guide the user to the destination through the calculated route. At an intersection on the calculated route, if a turn is necessary, the navigation system notifies the user which direction to turn at the intersection.
During the route guidance operation, the navigation system successively retrieves the map data associated with the calculated route from the data storage medium and stores such map data in a memory and reads the map data in the memory for conducting the route guidance operation. The map data for the navigation system must includes a vast amount of information such as road shapes, road classes, allowable speeds and other traffic regulations, POI (point of interest) information, POI icons, map icons, etc. Thus, the process of storing and retrieving such a large amount of map data during the route guidance operation can be time consuming and inefficient.
In order to resolves such burdens, the map data used for a navigation system is typically structured in a multiple layer data format. FIG. 1 is a schematic diagram showing an example of such a multiple layer data format of the map data used in the navigation system. As shown, the data format in FIG. 1 is configured by a layer 11A, a layer 11B, a layer 11C and a layer 11D each representing a part of the map data to be stored in a memory of the navigation system.
Further, the map data in each of the layers 11A-11D are divided into a plurality of meshes or mesh portions represented by reference numerals 13. Namely, the map data is hierarchically layered corresponding to the level of details of the map information as well as divided corresponding to the size or amount of the map data. In the example of FIG. 1, the higher the layer is, the lower the detailedness of the map information is and the larger the mesh size is.
Typically, the higher layer represents only high class roads, for example, interstate highway, freeway, etc. while the lower layer represents low class roads, i.e., residential roads, etc., POI icons, building foot prints, etc., in addition to that represented by the higher layers. One of the reasons for using the layered structure is to accommodate several different map scales for enlarging or shrinking the map image on the display screen on the navigation system. Since the lower layer includes more detailed map data, the size of the mesh portion 13 is smaller than that of the higher layer to maintain the amount of map data within a predetermined range.
In FIG. 1, although the same numerals 15 are used to indicate the roads, the classes of the roads represented by them are not the same. Namely, the roads 15 in the higher layers represent only the high class roads while the roads 15 in the lower layer includes all the classes of roads. Further, as noted above, the map data in each data layer is divided into a plurality of meshes or mesh portions 13 each having a rectangular shape of a predetermined size.
Since the map data is treated as a unit of mesh portion 13 as shown in FIG. 1, the navigation system does not have to process an excessively large amount of data at a time. The layer 11A shown in FIG. 1 is comprised of one mesh 13A while the layer 11B is comprised of four mesh portions 13B, and the layer 11C is comprised of eight mesh portions 13C while the layer 11D is comprised of sixteen mesh portions 13D. Thus, the performance limitation caused by the hardware capability of the navigation system can be avoided by maintaining the map data in the suitable size.
FIG. 2A is a schematic view showing the relationship between road links and nodes which are basic components for representing a road. FIG. 2B is a table showing an example of data word length for expressing each road link shown in FIG. 2A. As shown in FIGS. 2A and 2B, in the map data, each road in the corresponding mesh portions in the layers 11A-11D of FIG. 1 is divided into small components called road links or links where each road link is typically a relatively short straight line.
The end of each link is further connected to other links where a connection point is represented by a node which is defined by absolute position data, i.e., latitude/longitude. In the example of FIG. 2A, within a mesh portion 13D, a link 21A has a node 23A and a node 23B, a link 21B has the node 23B and a node 23C, and a link 21C has the node 23C and a node 23D. Thus, the links 21A and 21B are connected at the node 23B and the links 21B and 21C are connected at the node 23C.
Typically, in the map data, each link is uniquely identified by a link number and a mesh number in addition to the absolute position data of each node noted above and data for specifying the layer. The mesh number for an intended link is to identify a particular mesh portion in which the intended road link is located. Generally, a mesh number is expressed by a data word consisting of four-byte long and a link number is expressed by a data word consisting of eight-byte long as shown in the table in FIG. 2B.
Namely, in the table of FIG. 2B, each of the road links 21A-21C is identified by the mesh number of four bytes and the link number of eight bytes. Thus, in the example of FIG. 2B, it is necessary to use twelve bytes of data word to specify one road link. If the calculated route is long, the number of road links that constitute the calculate route becomes large, such as several thousands to several hundred thousand, which requires a large amount of data.
When a vehicle engine is turned-off during the route guidance operation, the navigation system will store the calculated route in a backup memory so that the route guidance can restart when the vehicle is turned-on again. However, as noted above, saving one link requires 12 bytes of map data, and saving the data corresponding to a long route consequently requires a large storage space due to the large data size. Thus, there is a need of a new method and apparatus for efficiently storing the map data on the calculated route in a memory of the navigation system.